package com.heima.leetcode.practice;

import java.util.LinkedList;

/**
 * leetcode 155. 最小栈
 * @author 勾新杰
 * @version 1.0
 * @date 2024/11/20 20:11
 */
public class E155 {

    /**
     * 最小栈
     */
    public static class MinStack {

        /**
         * 数据栈，正常的栈
         */
        private final LinkedList<Integer> dataStack;

        /**
         * 最小栈，具体元素分别对应数据栈相应层级及以下的最小值
         */
        private final LinkedList<Integer> minStack;

        /**
         * 初始化最小栈
         */
        public MinStack() {
            dataStack = new LinkedList<>();
            minStack = new LinkedList<>();
        }

        /**
         * push操作
         */
        public void push(int val) {
            // 1. 往数据栈中压栈
            dataStack.push(val);
            // 2. 往最小栈中压入数据栈当前层以下的最小值
            if (minStack.isEmpty()) minStack.push(val);
            else {
                Integer peek = minStack.peek();
                minStack.push(val < peek ? val : peek);
            }
        }

        /**
         * pop操作
         */
        public void pop() {
            dataStack.pop();
            minStack.pop();
        }

        /**
         * Get the top element.
         */
        public int top() {
            return dataStack.isEmpty() ? 0 : dataStack.peek();
        }

        /**
         * Retrieve the minimum element in the stack.
         */
        public int getMin() {
            return minStack.isEmpty() ? 0 : minStack.peek();
        }
    }
}
